import java.util.*;

public class SolutionOffer38 {
    public String[] permutation(String s) {
        Map<Character,Integer> map=new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c,map.getOrDefault(c,0)+1);
        }
        char[] chars=new char[s.length()];
        Set<String> stringSet=new HashSet<>();
        dfs(0,chars,stringSet,map);
        List<String> l=new ArrayList<>(stringSet);
        String[] ans=new String[l.size()];
        for (int i=0;i<ans.length;i++){
            ans[i]=l.get(i);
        }
        return ans;
    }

    void dfs(int k,char[] ans,Set<String> set,Map<Character,Integer> map){
        if (k==ans.length){
            set.add(String.valueOf(ans));
            return;
        }
        for (Map.Entry<Character,Integer> entry:map.entrySet()){
            if (entry.getValue()>0){
                ans[k]=entry.getKey();
                map.put(entry.getKey(),entry.getValue()-1);
                dfs(k+1,ans,set,map);
                map.put(entry.getKey(),entry.getValue()+1);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new SolutionOffer38().permutation("abc")));
    }
}
